package com.gaofeng.algo.java;

import java.util.*;

public class BFSJava {

    public int shortestBridge(int[][] A) {
        int row = A.length;
        int col = A[0].length;
        int[][] colors = getComponent(A);//深搜 获取所有的连通图
        ArrayDeque<Node> queue = new ArrayDeque<>();
        Set<Integer> target = new HashSet<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (colors[i][j] == 1) { //将第一个连通图添加到队列中去
                    queue.add(new Node(i, j, 0));
                } else if (colors[i][j] == 2) {
                    target.add(i * col + j);
                }
            }
        }

        //广搜使用队列来实现
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            //找到连通的后,就把结果返回
            if (target.contains(node.r * col + node.c)) {
                return node.depth - 1;
            }
            //遍历当前从队列中取出来的顶点的相邻顶点
            for (Integer neighbor : neighbors(A, node.r, node.c)) {
                int nr = neighbor / col;
                int nc = neighbor % col;
                //如果当前顶点的相邻顶点不在同一个连通图中
                if (colors[nr][nc] != 1) {
                    //将其添加到队列中去
                    queue.add(new Node(nr, nc, node.depth + 1));
                    //并将颜色标注为1表示在同一个连通中,
                    colors[nr][nc] = 1;
                }
            }
        }
        //没有最短的路径,就抛出异常,本题的案例是必然会找到的
        throw null;
    }

    private int[][] getComponent(int[][] a) {
        int row = a.length;
        int col = a[0].length;
        int id = 0;
        int[][] colors = new int[row][col];
        //使用深搜来获取不同的连通图
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (colors[i][j] == 0 && a[i][j] == 1) {
                    ArrayDeque<Integer> stack = new ArrayDeque<>();
                    stack.push(i * col + j);
                    colors[i][j] = ++id;
                    //利用栈进行深搜
                    while (!stack.isEmpty()) {
                        int node = stack.pop();
                        int r = node / col;
                        int c = node % col;
                        for (Integer neighbor : neighbors(a, r, c)) {
                            int nr = neighbor / col;
                            int nc = neighbor % col;
                            if (colors[nr][nc] == 0 && a[nr][nc] == 1) {
                                stack.push(nr * col + nc);
                                colors[nr][nc] = id;
                            }
                        }
                    }
                }
            }
        }
        return colors;
    }

    private boolean isArea(int[][] A, int i, int j) {
        int row = A.length;
        int col = A[0].length;
        return i >= 0 && i < row && j >= 0 && j < col;
    }

    private List<Integer> neighbors(int[][] a, int r, int c) {
        int R = a.length;
        int C = a[0].length;
        List<Integer> ans = new ArrayList<>();
        if (0 <= r - 1) ans.add((r - 1) * C + c);
        if (0 <= c - 1) ans.add(r * C + c - 1);
        if (r + 1 < R) ans.add((r + 1) * C + c);
        if (c + 1 < C) ans.add(r * C + c + 1);

        return ans;
    }


    class Node {
        public int r;
        public int c;
        public int depth;

        public Node(int r, int c, int depth) {
            this.r = r;
            this.c = c;
            this.depth = depth;
        }
    }
}
